The invention is directed to memory management systems for computer systems.
Computer memory management systems, particularly for real-time systems, should assure short access times and high file packing density. Further, data protection and availability are other critical demands made of such memory management systems.
A memory management system for managing a pool of data of variable lengths manages the memory space it manages in the form of memory blocks of different lengths. The lengths of the individual memory blocks derive from the sequence of memory requests and memory releases. Sub-sections that become free are united with adjoining, free subsections (this is known as smelting).
The memory management system usually makes use of an occupied list and a free list for the implementation of jobs. Various methods for searching the free list are known when assigning memories.
In what is referred to as the first-fit method, a search is started at the beginning of the memory space to be managed and the first block that is adequate in terms of length is allocated to the user.
In what is referred to as the next-fit method, the first block that is adequate in terms of length is likewise allocated to the user; the search, however, begins with that block that was last allocated to a user.
In what is referred to as the best-fit method, a search is carried out until that block comprising the smallest possible block that is adequate in terms of length has been found.
What is referred to as the buddy method is available as an alternative for memory management with an occupied list and a free list. The buddy method requires n free lists for the management of 2.sup.n byte of memory. Those free blocks having the size 2.sup.k are managed in a k.sup.th list. When a memory area having the length m is then requested, the smallest free block that is greater than m is halved until a further halving would yield a block smaller than m. One of the two blocks that arose in the last halving is occupied. The other blocks that arose in the halvings are entered into the respective free lists. Upon release of a block, blocks are respectively smelted until a further smelting is no longer possible because, for example, the second half is occupied. This smelting, however, is comparatively improbable since exactly two blocks of the same size must be free next to one another as a prerequisite. There is thus the tendency that larger blocks, i.e. blocks that are already rare are, in particular, no longer efficiently managed during ongoing operations.
The buddy system thus has the disadvantage that it leaves the memory unused between the actual request and the next-higher power of two.
A further disadvantage of the buddy system occurs in a protection-critical management structure where a great number of splittings and, thus, critical rechainings in the free chains can become necessary under certain circumstances for the occupation of a block having a "small" size. This is the normal case particularly at the beginning of the occupation.
The disadvantage of the best-fit method is the relatively long search times and frequent splitting/smelting.
The disadvantage of the first-fit method is that it requires a high frequency of splitting/smelting and results in too low of a file packing density.
A further alternative for the management of free memory is to use a dynamic tree sorted according to block lengths whose individual nodes accept the respective management data of a block. The critical advantage of this type of free memory management is a fast best-fit access when searching for a free block. At the same time, however, this type of management has the following, serious disadvantages:
In order to be able to maintain said advantage over the long-term, a regular rebalancing of the tree would be required. PA1 In general, a request or, respectively, release of a memory block (or, potentially, of a plurality of blocks) would involve a rebalancing of the tree. Access to the free memory management would have to be inhibited during this time. PA1 As a result of the needed rebalancing, the overall structure would often be manipulated to a great extent, as a result whereof the probability of chaining errors would greatly increase. An auditing increase would be necessary for compensation. PA1 For reasons of data protection, the dynamic tree would have to be kept semi-permanent. Every header modified in a rebalancing would thus appear as a location in the disk notebook linked with the corresponding transaction. PA1 The memory management system should be kept open with garbage collection in view of a possible expansion. In the case of a dynamic tree structure, the memory upheavals connected with the garbage collection would lead to substantial rechainings within the tree, which would in turn lead to the aforementioned problems. PA1 As a fundamental problem of a free memory management based on a best-fit search, an accumulation of small, relatively unusable blocks would occur, these deriving as fractions due to splitting (block splitting) in a preceding selection of blocks that were "somewhat" too large.